class Solution:
    def getMoneyAmount(self, n: int) -> int:
        dp = [[0] * (n + 1) for _ in range(n+1)]
        for i in range(n - 1, 0, -1):
            for j in range(i + 1, n + 1):
                min = 0xffff
                for k in range(i, j):
                    temp = k + max(dp[i][k-1],dp[k+1][j])
                    if temp < min:
                        min = temp
                dp[i][j] = min
        return dp[1][n]